#include<iostream>
#include<iterator>
#include<algorithm>
using namespace std;

void MergeSort(int* a, int i, int m, int n, int* b)  //a[i...m) + a[m...n) => a[i...n)
{
    int j = 0;
    int k = m;
    int t = i;
    
    for (; i < m && k < n; ++j)
    {
        if (a[i] < a[k])
        {
            b[j] = a[i++];
        }
        else
        {
            b[j] = a[k++];
        }
    }
    
    if (i < m)
    {
        copy(a + i, a + m, b + j);
    }
    else
    {
        copy(a + k, a + n, b + j);
    }
    
    copy(b, b + n - t, a + t);
}

int main(void)
{
    int array[] = {52, 49, 80, 36, 14, 58, 61, 23, 97, 75};
    int size = sizeof(array) / sizeof(array[0]);
    int* pTemp = new int[size];
    
    int offset = 1;
    while (offset < size)
    {
        int i = 0;
        int j = offset;
        int k = offset * 2;
        
        while (j < size)
        {
            int endPos = k < size ? k : size;
            
            MergeSort(array, i, j, endPos, pTemp);
            
            i = k;
            j = i + offset;
            k = j + offset;
        }
        
        offset *= 2;
    }
    
    copy(array, array + size, ostream_iterator<int>(cout, " "));
    
    system("pause");
}
